package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

public class g封闭式求解other我的理解是运用数学思想求出特殊问题的通解公式 {
	public static void main(String[] args) {
		g封闭式求解other我的理解是运用数学思想求出特殊问题的通解公式 test = new g封闭式求解other我的理解是运用数学思想求出特殊问题的通解公式();
		long res1 = test.HanoiFormula(3);
		System.out.println(res1);
		try {
			long res2 = test.FibonacciSequenceFormula(15);
			System.out.println(res2);
			long res3 = test.FibonacciSequenceFormulaFor3(20190324);
			System.out.println(res3);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	/**
	 * 汉诺塔的通解
	 * 默认底座数量 = 3
	 * f(n) = f(n - 1) + 1 + f(n - 1)
	 * 由数学归纳可得，当plateNumber = n
	 * 移动的次数是2^n - 1
	 * @param plateNumber 盘子数量
	 * @return
	 */
	public long HanoiFormula(int plateNumber) {
		long res = (long) (Math.pow(2, plateNumber) - 1);
		return res;
	}
	
	/**
	 * 斐波那契额数列通解
	 * [f(1),f(2)] 就是 [1,1]
	 * [1,1] * [0,1] 的n-1次方 = [f(n),f(n+1)]
	 * 		   [1,1]
	 * [1,1] * [0,1] 的n-2次方 = [f(n-1),f(n)]
	 * 		   [1,1]
	 * @param n
	 * @return
	 * @throws Exception
	 */
	public long FibonacciSequenceFormula(int n) throws Exception {
		long[][] matrix = new long[][] {
			{0, 1},
			{1, 1}
		};
		long[][] unit = new long[][] {
			{1, 1}
		};
		long[][] res = matrixPowerN(matrix, n - 2);
		res = matrixMultiply(unit, res);
		return res[0][1];
	}
	
	/**
	 * [1,1,1] * [0,0,1]  的n-3次方 = [f(n-2),f(n-1),f(n)]
	 * 		     [1,0,1]
	 * 			 [0,1,1]
	 * @param n
	 * @return
	 * @throws Exception
	 */
	public long FibonacciSequenceFormulaFor3(int n) throws Exception {
		long[][] matrix = new long[][] {
			{0, 0, 1},
			{1, 0, 1},
			{0, 1, 1}
		};
		long[][] unit = new long[][] {
			{1, 1, 1}
		};
		long[][] res = matrixPowerN(matrix, n - 3);
		res = matrixMultiply(unit, res);
		return res[0][2];
	}
	
	/**
	 * 默认是
	 * 能一次爬1阶
	 *  能一次爬2阶
	 *  能一次爬3阶
	 *  这三种基本条件
	 *  
	 *  那么stairsNumber = n
	 *  就有2^(n-1)个爬楼梯方法
	 * @param n
	 * @return
	 */
	public long climbStairsFormula(int stairsNumber) {
		long res = (long) Math.pow(2, stairsNumber - 1);
		return res;
	}
	
	public long[][] matrixPowerN(long[][] matrix, int n) throws Exception {
		long[][] res = new long[matrix.length][matrix[0].length];
		for (int i = 0; i < res.length; i++) {
			res[i][i] = 1;
		}
		long[][] helper = matrix;
		while (n != 0) {
			if ((n & 1) != 0) {
				res = matrixMultiply(res, helper);
			}
			helper = matrixMultiply(helper, helper);
			n = n >>> 1;
		}
		return res;
	}
	
	public long[][] matrixMultiply(long[][] A, long[][] B) throws Exception {
		int Arow = A.length;
		int Acol = A[0].length;
		int Brow = B.length;
		int Bcol = B[0].length;
		if (Arow == 0 || Brow == 0 || Acol == 0 || Bcol == 0) {
			throw new Exception();
		} else if (Acol != Brow) {
			throw new Exception();
		}
		long[][] res = new long[Arow][Bcol];
		for (int row = 0; row < Arow; row++) {
			for (int col = 0; col < Bcol; col++) {
				for (int current = 0; current < Acol; current++) {
					res[row][col] += A[row][current] * B[current][col];
				}
			}
		}
		return res;
	}
}
